package com.ls.day7;

import java.lang.reflect.Array;
import java.util.*;


//双指针法
public class ThreeSum {

    public static void main(String[] args) {
        List<List<Integer>> items = threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        for (List<Integer> item:items){
            for (Integer a:item){
                System.out.print(a+" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> items = new ArrayList<>();

        Arrays.sort(nums);

        for (int i=0;i<nums.length;i++){
            if(nums[i]>0) return items;

            if(i>0 && nums[i]==nums[i-1]) continue;     //去重

            int L = i+1, R=nums.length-1;
            while (L<R){
                int tem = nums[i]+nums[L]+nums[R];

                if(tem==0){
                    List<Integer> item = new ArrayList<>();
                    item.add(nums[i]);
                    item.add(nums[L]);
                    item.add(nums[R]);
                    items.add(item);
                    while(L < R && nums[L+1] == nums[L]) ++L;
                    while (L < R && nums[R-1] == nums[R]) --R;
                    ++L;
                    --R;
                }else if(tem<0) {
                    L++;
                }else R--;
            }
        }
        return items;
    }
}
